Wojek 0.7.9 - Automatyczny regionalizator

Download:

Opis:

Zmiany:

v0.7.9 - 03.10.2009
- Obsługa 3bajtowych typów
- Poprawki dla kompilacji pod Ubuntu i/lub 64bit systemów

v0.7.8 - 04.04.2008
- Naprawa obsługi zagranicznych wysp (Segmentation fault).
- Przywrócenie slownik.txt z wersji 0.7.6 z powodu upapranych plznaczkow(11.05.2008)

v0.7.7 - 20.10.2007
- Zmiany zapisu końca linii, aby pod Linuksem nie było ^M (\r\n) by Tomek.

v0.7.6 - 31.08.2007
- zwiększenie tolerancji na blędy analizowanej mapy obietków. Nieprawidłowości powodują jedynie zignorowanie
  aktualnego obiektu (+informacja na stderr) zamiast przerywanie całego procesu.
- wyłączenie ignorowania dla niepewnych polyline. Wcześniej był warning i obiekt nic nie dostawał
...

Readme.txt:

Wojek - automatyczny regionalizator

        Bardzo skrótowa dokumentacja.

Program służy automatycznemu przypisaniu atrybutów związanych z położeniem
na mapie. Program na podstawie mapy obszarów oraz słownika przypisuje
zestaw atrybutów związanych z obszarem, do którego należy dany punkt.

Głównym przeznaczeniem programu jest automatyczne dodawanie RegionName= oraz CountryName=
obiektom podlegającym indeksacji w mapach projektu UMP-pcPL.

        Działanie

Program działa potokowo, czyli aby obrobić plik input.mp i wynik zapisać do
output.mp wywołujemy:
./wojek.exe -s slownik.txt -k obszary.mp -e err.wpr < input.mp > output.mp
Można również użyć parametrów -f i -F do wskazania plików, zamiast używać przekierowania potoków (<,>):
./wojek.exe -s slownik.txt -k obszary.mp -e err.wpr -f input.mp 0F output.mp

        Parametry wywołania:

-h : pomoc
-d : miejscami więcej komunikatow (debug)
-s slownik.txt : podanie ścieżki do pliku słownika
-k obszary.mp : podanie ścieżki do pliku z definicją obszarów w nowej konwencji (poi+linie)
-o obszary.mp : podanie ścieżki do pliku z definicją obszarów
-e errors.wpt : podanie ścieżki do pliku wynikowego do rysowania punktów
                problematycznych (i błędów)
-g wartosc : włączenie znajdowania obiektów w okolicy granic oraz ustawienie
             szerokości poszukiwań na wartość (np 0.004)
-p : obrabiaj jedynie [POI] (miasta i POI z "Miasto=xxx")
-n : wzbogacaj rowniez nienazwane ulic
-u : szukaj miast duplikatow (o tych samych nazwach w wojewodztwie)
-z zap_obszar.mp : zapisz wczytany obszar w reprezentacji kreskowej
-f input.mp : plik wejsciowy (domyslnie standardowe wejscie)
-F output.mp : plik zapisu wyniku (domyslnie standardowe wyjscie)

W pliku podanym po opcji -e zapisywane są położenia punktów lub miejsc,
gdzie stwierdzono problem. Etykieta rozpoczyna się od kilkuznakowego
przedrostka i liczby porządkowej. Typowe przedrostki:
- X : problematyczny odcinek granicy
- P : lista srodkow odcinkow, ktore lezaly w przedziale z
      problematycznym odcinkiem oznaczonym X
- G : wykryty punkt w obszarze przygranicznym (opcja -g)
- F : punkt poza granicami obszarow
- B : punkt po środku granicy miedzy obszarami
- E : przypisany obszar punktu nie nalezy do słownika obszarów
- C : Cross - polyline nie jest zdecydowanie (powyżej ustalonego limitu w pliku slownika)
      w którymś z obszarów. WPT jest stawiany na środku pierwszego odcinka polylina


        Wybór obiektów do przetwarzania

Aktualnie program obrabia tylko obiekty typu punkt lub polyline. Obiekty podlegajace
wzbogaceniu o regionalne informacje sa wybierane poprzez filtracje na podstawie
ciagu znakow wystepujacych w definicji obiektu i przez typ. W pliku konfiguracyjnym
slownika sa nastepujace parametry sterujace wyborem obiektu:
_AllowedTypes - lista typów lub przedziałów typów dozwolonych do opisu
_ObjectDetector - lista kluczy wyszukiwanych, które klasyfikują obiekt do opisania
_ObjectAvoider - lista kluczy zabraniających opisywać obiekt (w razie dopasowania zasłania pozostałe filtry)

Pozycje na tych listach są pooddzielane średnikami. Klucze z _ObjectDetector i _ObjectAvoider
są porównywane z liniami tekstu obiektu, a zgodność jest badana wg całej linii.
W przypadku kluczy zakończonych * istotna jest zgodność klucza z początkiem linii oraz warunek, że
analizowana linia jest dłuższa (unikanie pustych definicji np 'Miasto=' bez podania miasta).

Przykładowe ustawienia:
_ObjectDetector     : City=Y;Miasto=*
_ObjectAvoider      : RegionName=*
_AllowedTypes       : 0x0;0x01;0x2-0x7fff;0x8000-0xffff
Program będzie w takim przypadku unikał obiektów już opisanych regionem, a wzbogacał tylko
miasta (City=Y) oraz te obiekty, które mają niepusty parametr Miasto=... .
Typ w tym wypadku został ustawiony na cały dostępny zakres przy pomocy różnych zapisów,
aby pokazać jak można określać ten parametr.

Opis pozostałych opcji i formatu slownika znajduje się w komentarzach w pliku slownik.txt


        Format opisu obszarów

Program obsługuje 3 konwencje opisu danych o obszarach w pliku mapy.
1) Granice opisane nazwanymi kreskami ([POLYLINE])
2) Granice opisane nazwanymi obszarami ([POLYGON])
3) Granice opisane kreskami z nazwanymi punktami próbnymi ([POLYLINE] + [POI])

Formaty 1,2 są obsługiwane przez podanie mapy jako parametry -o
Format 3 jest podawany przez opcję -k

Dane tworzące mapę obszarów muszą spełniać wiele warunków, aby były poprawnie
interpretowane przez automatyczny proces przypisywania regionów. Podstawowe
zakazy obejmują: brak przecinania, brak wolnych końców, spójność logiczna,
dane rysowane na poziomie 0 (Data=). Pętle pewnie by działały, ale lepiej podzielić
na dwie części.
Nie ma natomiast znaczenia typ obiektów, jedynie ich rodzaj (punkt/obszar/krecha).
Przynajmniej na razie :)

Format 1):
Format ten był koncepcyjnie pierwszym i pod kątem którego pisano program, jednak nie jest wygodny.
O ile łatwo przesuwać, to dodanie nowego obszaru wymaga zmian nazw dwuczłonowych w koło.
- Obszary definiowane są jako zbiór krawędzi z dwuczłonową nazwą, po jednym członie
  dla każdego z sąsiadujących obszarów. Człony oddzielone są znakiem /.
- Pierwszy człon określa zewnętrze, drugi wnętrze, jeśli rysowalibyśmy zgodnie z ruchem
  wskazówek zegara
- Każdy obiekt musi zawierać nazwę zawierającą / (zewnętrze można oznaczać np przez -)
- granica nie może wychodzić poza krawędz styku dwóch (dokłanie dwóch) obszarów które opisuje
-

Format 2):
Format powstały w wyniku potrzeb (akurat tak był zapisany jeden plik). Trudno rysować, trudno edytować,
trudno modyfikować.
- Obszary opisywane są wielokątami z nazwą (Label=)
- nazwa obszaru okresla zawartosc obszaru wewnatrz, jesli punkty sa rysowane
  zgodnie z ruchem wskazowek zegara (odwrotnie niz dla kresek, sorry ;) )
- obszar moze byc zawarty w obszarze, o ile ten drugi jest dziurawy (dziura dokładną kopią wewnętrznego
  z odwróconym kierunkiem)
  Zatem aby zrobic dziure z innym obszarem, nalezy :
  + narysowac obszar Z zgodnie z ruchem zegara
  + narysowac obszar W wewnatrz Z zgodnie z ruchem zegara
  + skopiowac W, odwrocic kierunek i nadac nazwe Z (czyli zrobic dziure
    bedaca dokladna kopia W z dokladnoscia do kierunku)
- Obszary nie moga sie przecinac.
- obszary nie moga sie samoprzecinac (wielokat prosty ma byc)
- aby program widzial granice, obszary musza przylegac co do punkta (bez jakichkolwiek odstepst)

Format 3): (sugerowany)
Ten format powstał w celu ułatwienia rysowania lub importu mapy obszarów, w których dane nie są
na tyle uporządkowane, by łatwo dało się je przekształcić w jeden z pierwszych dwóch formatów. Poza
tym ideą dodania było ułatwienie edycji istniejącej mapy przez proste dodawanie nowych obszarów i
podobszarów bez konieczności modyfikacji dużej ilości istniejąch danych.
- Dane zapisane są jako zbiór kresek tworzących granice (ich nazwy i typ są ignorowane) oraz
zbioru punktów wewnątrz obszarów. Nazwa punktów określa nazwę obszaru w którym znajduje się punkt.
- kreski mogą być w dowolnych kierunkach i ilości (ze względu na wydajność, lepiej by krawędź między
dwoma obszarami była ciągła niż podzielona na milion kawałków, ale dla rezultatu nie ma znaczenia)
- Dla każdego punktu znajdowana jest krawędz dokładnie nad punktem i okrążana w celu nazwania obszaru.
  Zatem pojedynczy punkt przypisuje jeden z dwóch członów nazwy dla zamkniętego obszaru zaczynając
  ponad punktem.
- W danym zamkniętym obszarze nie może być więcej niż jeden punkt. W przypadku wysp punkt może
być zarówno pod wyspą jak i obok (wcześniej wymagane były dwa punkty, teraz tylko jeden):
-----------------------------
|                           |
|    ------------           |
|    |          |      Z    |
|    |    W     |           |
|    |          |           |
|    ------------           |
|                           |
-----------------------------



W przypadku wykrycia problemow z granicami (dotyczy formatu 1,2), program wyswietli
zawartosc danego pasa, dla ktorego odcinki nie tworza spojnego podzialu na obszary.
Przykladowy problem literowki:

 P3: ["-" {(16.6374,49.729)->(17.7155,49.6064)} "Czechy"],
 P4: ["Czechy" {(17.3897,50.283)->(17.4011,50.2796)} "opolskie"],
 P5: ["opolskie" {(17.3828,50.8755)->(17.3945,50.8744)} "dolnoslaskie"],
 P6: ["dolnoslaskie" {(17.3543,50.9)->(17.3945,50.8897)} "opolskie"],
 P7: ["opolskie" {(17.3902,50.9233)->(17.3983,50.9229)} "dolnoslaskie"],
 P8: ["dolnoslaskie" {(17.3823,51.6355)->(17.4,51.634)} "wielkopolskie"],
 P9: ["wielkopolskie" {(17.3674,52.9743)->(17.3937,52.9835)} "kujawsko-pomorskie"],
 P10: ["kujawsko-pomorskie" {(17.387,53.2291)->(17.403,53.2272)} "wielkopolskie"],
 P11: ["wielkopolskie" {(17.3853,53.2993)->(17.3968,53.2958)} "kujawsko-pomorskie"],
> tu cos nie tak >
 P12: ["kujawsko-spomorskie" {(17.3916,53.4918)->(17.3935,53.5021)} "pomorskie"],
 P13: ["pomorskie" {(17.3909,53.5078)->(17.3935,53.5021)} "kujawsko-spomorskie"],
 P14: ["kujawsko-spomorskie" {(17.3909,53.5078)->(17.4007,53.513)} "pomorskie"],
 P15: ["pomorskie" {(17.362,54.7529)->(17.4254,54.7552)} "-"],

Nazwa koncowa fragmentu jest poczatkiem kolejnego. Przy pomocy "-" oznaczonono
"zagranice" w przykladowym pliku wojewodztwa.mp, a {..} wypelnione jest
wspolrzednymi odcinka. P* okresla nazwe waypointa w generowanym pliku bledow.
Najczestsze przyczyny problemow:
- trzy granice nie spotykaja sie we wspolnym punkcie (wtedy na liscie
  pojawia sie fragment, ktorego usuniecie naprawiloby kolejnosc)
- zly kierunek jednej z granic (wtedy jeden z elementow jest na odwrot
  i psuje kolejnosc)
- literowka w nazwie jednej z granic



Uwaga: granice zapisane jako obszary wczytuja sie zdecydowanie wolniej niz granice
zapisane jako kreski z dwuczlonowymi nazwami. Wynika to z koniecznosci okreslenia dla
kazdego odcinka jakie obszary sa po obu jego stronach. Przy bardzo skomplikowanych
danych bedzie to mialo mniejsze znaczenie. Przykladowe porownanie czasu wczytania
granic wojewodztw o podobnym stopniu skomplikowania (ok 20k punktow):
- zapis obszarami: 0.7s
- zapis granicami: 0.18s
dla bardziej skomplikowanej mapy (ok 83k punktow, 380 obszarow):
- zapis obszarami: 1.9s
- zapis granicami: 1.2s
Jest możliwość zapisu wczytanej mapy (np obszarowej) w zwarty sposób w zapisie
granicowym przy pomocy opcji -z. Każda granica między dwoma obszarami jest wtedy jako jeden objekt
(ew. podzielony na kilka linijek Data0= po 500 punktow jeśli przy długa).
Można to wykorzystać do konwersji granic zapisanych obszarowo, na szybsze kreskowe.
Zapis nie jest do końca przetestowany, ale "najczęściej" działa ;)


Obiekty o tej samej nazwie (zarowno obszary jak i krechy) moga byc polaczone
w jednym bloku [XXX]...[END]. Wtedy kazde wystapienie Data0=...
jest traktowane jako obiekt o nazwie Label=.. z poczatku bloku.

UWAGA: Mapa moze zawierac jedynie albo granice kreskowe, albo obszarowe. Jesli sie wie co zrobic
mozna by mieszac, ale tlumaczenie tego jak nie zrobic sobie przy tym kuku wybiega mocno poza
ten za dlugi opis.

Proponowanym formatem jest jednak ostatni, czyli granice kreskowe z punktami nazywającymi
wewnątrz obszarów, gdyż jest mniej restykcyjny i łatwiejszy w edycji.

Program aktualnie nie lubi granic idealnie pionowych i jesli punkt lezy na takiej
granicy lub w poblizu to dla programu tak jak by tej granicy nie bylo. Decyzja jest na
podstawie najblizszego odcinka nad punktem, wiec nie ma duzego problemu, ale wyszukiwanie
przygranicznikow nie bedzie juz w takich miejscach zawsze poprawne.

Jako czynność zaradczą, program przesuwa minimalnie środek takich odcinków
(o ok 0.000005, czyli poniżej dokładności 5 miejsc po przecinku), tak aby w ten sposób
znajdowanie punktów w pobliżu granicy działało prawidłowo.

Uwaga: Program ma uproszczoną procedurę czytania z pliku mapy i może mieć problem
z liniami dłuższymi niż 650000 znaków. W przypadku pliku słownika ograniczenie wynosi ok 1024 znaki.

        Istota dzialania programu:

- Mapa dzielona jest na poziome pasy (przedzialy) tak, aby w danym fragmencie
nie bylo zadnego punktu poczatkowego lub koncowego odcinkow granicy.
Zatem zbior wszystkich punktow tworzacych granice wyznacza punkty podzialu plaszczyzny na pasy.
- W kazdym pasie odcinki granicy zawierajace dany pas sa posortowane rosnaco.
- okreslenie przynaleznosci sprowadza sie do znalezienia najblizszego fragmentu granicy nad punktem przez:
  + znalezienie pasa (przedzialu), do ktorego nalezy punkty (wyszukiwanie binarne, bo przedzialy posortowane)
  + w obrebie pasa znalezienie odcinka ponad punktem(wyszukiwanie binarne, bo odcinki posortowane i nie przecinaja sie)

Punky na granicy uzyskuja status BETWEEN, natomiast punkty poza granicami
uzyskuja status OUTSIDE. Reszta ma status INSIDE i określoną nazwę obszaru, do ktorego naleza.

W przypadku obiektów typu [POLYLINE] przynależność jest określana z dokładnością
do pewnego progu ustawianego w pliku słownika ustawień. Każdy odcinek kreski jest
sprawdzany pod kątem przynależności jego środka do jednego z obszarów i jego długość
jest wliczana do udziału należenia kreski dla danego obszaru. Obszar, w którym
udział całej kreski jest większy niż próg, jest obszarem do którego należy polyline.
Jeśli dany odcinek jest dłuższy niż ustalone maksimum (_PolylineMaxSegments),
to jest dzielony na dostatecznie małe fragmenty.

UWAGA: program jest zoptymalizowany dla współrzędnych z obszaru Polski o 5 miejscach po przecinku:
- zakłada 2 cyfry przed kropką
- zakłada 5 (zawsze pięć, nawet zera) miejsc po przecinku.
Założenia te są prawdziwe dla Polski i pozwalają łatwo i szybko wczytywać dane o współrzędnich.
Przywrócenie obsługi dowolnego formatu zapisu współrzędnych zwiększyło by czas działania o 5-10%
(w common.h jest flaga USE_FAST_POINT_PARSE, którą można zmienić na 0, by wczytywać uniwersalnie)

Marcin Rudowski
mrudowski1  na  gmail.com